package com.zhanghp.class01.sort;

import static com.zhanghp.class01.sort.utils.SortUtils.*;

/**
 * 冒泡排序
 *
 * @author zhanghp
 * @date 2023/7/27 12:48
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = rand(10);
        printArr(arr);
        bubbleSortOptimize(arr);
        printArr(arr);
    }

    /**
     * 冒泡排序
     *
     * @param arr 乱序数组
     */
    public static void bubbleSort(int[] arr) {
        // 边界条件
        if (arr == null || arr.length < BOUNDERY_LENGTH) {
            return;
        }
        // 0 ~ N
        // 0 ~ N-1
        // 0 ~ N-2
        for (int end = arr.length - 1; end >= 0; end--) {
            for (int i = 0; i <= end; i++) {
                while (i + 1 < arr.length && arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }

    /**
     * 优化
     *
     * @param arr 乱序数组
     */
    public static void bubbleSortOptimize(int[] arr) {
        // 边界条件
        if (arr == null || arr.length < BOUNDERY_LENGTH) {
            return;
        }
        // 0 ~ N
        // 0 ~ N-1
        // 0 ~ N-2
        for (int end = arr.length - 1; end >= 0; end--) {
            for (int i = 0; i < end; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }

    /**
     * 这个严格意义来说，不符合冒泡排序的概念
     * 0~N: 挨个和最后一个作比较，所以不符合
     *
     * @param arr 乱序数组
     */
    public static void bubbleSort2(int[] arr) {
        // 边界条件
        if (arr == null || arr.length < BOUNDERY_LENGTH) {
            return;
        }
        // 0 ~ N
        // 0 ~ N-1
        // 0 ~ N-2
        for (int end = arr.length - 1; end >= 0; end--) {
            for (int i = 0; i <= end; i++) {
                if (arr[end] < arr[i]) {
                    swap(arr, end, i);
                }
            }
        }
    }
}
